// https://leetcode.cn/problems/domino-and-tromino-tiling/

long long mod = 1e9 + 7;

//dp[n] = dp[n - 1] + dp[n - 2] + 2 * dp[n - 3] + 2 * dp[n - 4]
int numTilings(long long n) {
    vector<vector<long long>> dp(n + 1, vector<long long>(2));
    dp[0][0] = dp[1][0] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1]) % mod;
        if (i >= 2) {
            dp[i][1] = (dp[i - 2][0] * 2 + dp[i - 1][1]) % mod;
        }
        cout << dp[i][0] << endl;
    }
    return dp[n][0];
}